#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>

using namespace std;

// 最大子数组和
class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        // dp[i]:表示以i位置为结尾的最大子数组和
        int n = nums.size();
        vector<int> dp(n);
        int ans = INT_MIN;
        dp[0] = nums[0];
        for (int i = 1; i < n; i++)
        {
            dp[i] = max(nums[i], nums[i] + dp[i - 1]);
            ans = max(ans, dp[i]);
        }

        return max(dp[0], ans);
    }
};

// 合并区间
class Solution
{
public:
    vector<vector<int>> merge(vector<vector<int>> &intervals)
    {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> ans;
        int left1 = intervals[0][0], right1 = intervals[0][1];
        int n = intervals.size();
        for (int i = 1; i < n; i++)
        {
            int left2 = intervals[i][0], right2 = intervals[i][1];
            if (left2 > right1)
            {
                ans.push_back({left1, right1});
                left1 = left2;
                right1 = right2;
            }
            else
            {
                left1 = min(left1, left2);
                right1 = max(right1, right2);
            }
        }
        ans.push_back({left1, right1});
        return ans;
    }
};

// 轮转数组
class Solution
{
public:
    void rotate(vector<int> &nums, int k)
    {
        int n = nums.size();
        k %= n;
        vector<int> tmp;
        for (int i = n - k; i < n; i++)
        {
            tmp.push_back(nums[i]);
        }
        for (int i = n - k - 1; i >= 0; i--)
        {
            nums[i + k] = nums[i];
        }
        for (int i = 0; i < k; i++)
        {
            nums[i] = tmp[i];
        }
    }
};

// 除自身以外数组的乘积
class Solution
{
public:
    vector<int> productExceptSelf(vector<int> &nums)
    {
        int n = nums.size();
        // f[i]:表示i位置之前的乘积,g[i]:i位置之后的乘积
        vector<int> f(n), g(n), ans(n);
        f[0] = g[n - 1] = 1;
        for (int i = 1; i < n; i++)
        {
            f[i] = f[i - 1] * nums[i - 1];
        }
        for (int i = n - 2; i >= 0; i--)
        {
            g[i] = g[i + 1] * nums[i + 1];
        }

        for (int i = 0; i < n; i++)
        {
            ans[i] = f[i] * g[i];
        }

        return ans;
    }
};

// 缺失的第一个正数
class Solution
{
public:
    int firstMissingPositive(vector<int> &nums)
    {
        int n = nums.size();
        for (auto &x : nums)
        {
            if (x <= 0)
                x = n + 1;
        }

        for (int i = 0; i < n; i++)
        {
            int num = abs(nums[i]);
            if (num <= n)
            {
                nums[num - 1] = -abs(nums[num - 1]);
            }
        }

        for (int i = 0; i < n; i++)
        {
            if (nums[i] > 0)
            {
                return i + 1;
            }
        }

        return n + 1;
    }
};

class Solution
{
public:
    int firstMissingPositive(vector<int> &nums)
    {
        unordered_set<int> hash;
        for (auto x : nums)
            hash.insert(x);
        int n = nums.size();
        for (int i = 1; i <= n; i++)
        {
            if (!hash.count(i))
            {
                return i;
            }
        }
        return n + 1;
    }
};

// 矩阵置零
class Solution
{
public:
    void setZeroes(vector<vector<int>> &matrix)
    {
        int m = matrix.size(), n = matrix[0].size();
        vector<bool> row(m), col(n);
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (matrix[i][j] == 0)
                {
                    row[i] = col[j] = true;
                }
            }
        }
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (row[i] || col[j])
                {
                    matrix[i][j] = 0;
                }
            }
        }
    }
};